#include <stack>
#include <iostream>
#include "tree_traversal.h"

void postorder_traversal_recursive(Node * n) {
	if(n){
		postorder_traversal_recursive(n->left);
		postorder_traversal_recursive(n->right);
		std::cout << n->key << ' ';
	}
}

void postorder_traversal_stack(Node * n ) {
	std::stack<Node*> s;
	s.push(n);
	Node * prev = nullptr;
	while(!s.empty()) {
		Node * curr = s.top();
		if ( prev == curr->left ) {
			if ( curr->right ) {
				s.push(curr->right);
			} else {
				std::cout << curr->key << ' ';
				s.pop();
			}
		}
		else if ( prev == nullptr || prev->left == curr || prev->right == curr ) { //prev is curr's parent
			if (curr->left) {
				s.push(curr->left);
			}
			else if (curr->right) {
				s.push(curr->right);
			}
			else {
				std::cout << curr->key << ' ';
				s.pop();
			}
		}
		else if (prev == curr->right) {
			std::cout << curr->key << ' ';
			s.pop();
		}
		else {
			std::cout << "Unreachable\n";
		}
		prev = curr;
	}
}

void postorder_traversal_parent(Node * root) {
	Node * curr = root;
	Node * prev = nullptr;
	while (curr != nullptr) {
		if ( prev == nullptr || prev == curr->parent ) {
			prev = curr;
			if (curr->left) {
				curr = curr->left;
			} 
			else if (curr->right) {
				curr = curr->right;
			}
			else {
				std::cout << curr->key << ' ';
				curr = curr->parent;
			}
		}
		else if (curr->left == prev ) {
			prev = curr;
			if ( curr->right ) {
				curr = curr->right;
			}
			else {
				std::cout << curr->key << ' ';
				curr = curr->parent;
			}
		}
		else if (curr->right == prev) {
			prev = curr;
			std::cout << curr->key << ' ';
			curr = curr->parent;
		}
		else {
			throw "Nonreachable";
		}
	}
}

void postorder_reverse_preorder(Node* root){
	std::stack<Node*> s1;
	std::stack<Node*> s2;
	s1.push(root);
	while (!s1.empty()) {
		Node * n = s1.top(); s1.pop();
		s2.push(n);
		if(n->left)
			s1.push(n->left);
		if(n->right)
			s1.push(n->right);
	}
	while (!s2.empty() ) {
		Node * n = s2.top(); s2.pop();
		std::cout << n->key << ' ';
	}
}